package hebClustering.clusteringAlgorithms;

import hebClustering.Cluster;
import hebClustering.ClusterSet;
import hebClustering.vectorSpace.IVector;
import hebClustering.vectorSpace.distances.IDistance;

import java.util.Collection;

/**
 * Implementation of the clustering algorithm Bisecting K-means.
 * 
 * The algorithm operates in a greedy way.
 * It perform K-1 iterations and on each iteration it splits the worst cluster in the set into
 * two clusters using the {@link KMeansClustering K-Means algorithm}.
 * 
 * @see KMeansClustering
 */
public class BisectingKMeansClustering implements IClusteringAlgorithm {

	int K;
	IDistance distance;
	
	public BisectingKMeansClustering(int K,IDistance distance){
		this.K = K;
		this.distance = distance;
	}
	
	@Override
	public ClusterSet cluster(Collection<IVector> dataSet) {

		ClusterSet clusterSet = new ClusterSet();
		Cluster firstCluster = new Cluster();
		
		firstCluster.addAll(dataSet);
		clusterSet.add(firstCluster);
		
		for(int i=1; i<K; i++){
			Cluster worst = pickWorstCluster(clusterSet);
			split(clusterSet,worst);
		}
		
		return clusterSet;
	}

	private Cluster pickWorstCluster(ClusterSet clusterSet) {
		Cluster worst = new Cluster();
		
		clusterSet.quality();
		
		for(Cluster cluster : clusterSet){
			if(cluster.getSSE()>worst.getSSE())
				worst = cluster;
		}
		
		return worst;
	}

	private void split(ClusterSet clusterSet, Cluster worst) {
		IClusteringAlgorithm kMeans = new KMeansClustering(2, 50, distance);
		ClusterSet bestCut = kMeans.cluster(worst);
		
		for(int i = 0; i<3; i++){
			ClusterSet cut = kMeans.cluster(worst);
			if(bestCut.quality()<cut.quality())
				bestCut = cut;
		}
		
		clusterSet.remove(worst);
		clusterSet.addAll(bestCut);
	}

}
